﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.IsValidBST
{
    class MainProject
    {
        static void Main(string[] args)
        {
            //TreeNode treeNode = new TreeNode(5,new TreeNode(4),new TreeNode(6,new TreeNode(3),new TreeNode(7)));
            TreeNode treeNode = new TreeNode(2147483647,new TreeNode(2147483647));
            Console.WriteLine(IsValidBST(treeNode));
            Console.WriteLine(Math.Pow(2,31));
            Console.WriteLine(int.MaxValue);
            Console.WriteLine(int.MinValue);
            Console.ReadKey();
        }
        //DFS(需要给每个结点添加一个取值范围)
        public static bool IsValidBST(TreeNode root)
        {
            if (root.left == null && root.right == null)
            {
                return true;
            }
            return DFS(root, long.MinValue, long.MaxValue);
        }

        public static bool DFS(TreeNode treeNode, long min, long max)
        {
            if (treeNode == null)
            {
                return true;
            }

            //if (treeNode.val == int.MinValue || treeNode.val == int.MaxValue)
            //{
            //    return true;
            //}

            if (treeNode.val >= max || treeNode.val <= min)
            {
                return false;
            }

            return DFS(treeNode.left, min, treeNode.val) && DFS(treeNode.right, treeNode.val, max);
        }
    }
}
